1. Field of the Invention
The present invention relates to improvements in high speed multiply apparatus which minimizes latch requirements and I/O pin requirements between chips while attaining substantially the same operation speed as that of a conventional high speed multiply apparatus using a carry-save adder tree and a carry propagate adder.
2. Description of the Prior Art
U.S. Pat. No. 3,515,344 provides a high speed multiplier using a carry-save adder tree. A plurality of carry save adder stages, each comprised of one or more carry save adder units are arranged in a configuration which permits the summation of a plurality of plural-binary bit operands. Successive pluralities of operands are applied to the adder prior to the generation of a final sum for the plurality of operands previously applied.
"The IBM System/370 Model 91: Floating-Point Execution Unit" by S. F. Anderson et al, IBM Journal of Research and Development, January 1967, pp. 34-53, also provides the same high speed multiplier as that disclosed in the above-mentioned U.S. Pat. No. 3,515,344.
"4-2 Carry-Save Adder Implementation Using Send Circuits" by D. T. Shen et al, IBM TDB Vol. 20, No. 9, February 1978, pp. 3594-3597, shows a 4-2 carry-save adder.
"Multiplier Decoding With Look-Ahead" by A. Weinberger, IBM TDB Vol. 20, No. 9, February 1978, pp. 3591-3593 shows how to reduce the number of multiplier decoder outputs, gating in the selection of multiplicand multiples, and loading on multiplicand bits without reducing performance.
"A Comparison of Two Approaches to Multi-Operand Binary Addition" by D. E. Atkins et al, Proceedings 4th Symposium on Computer Arithmetic, Oct. 25-27, 1978, IEEE Catalog No. 78 CH 1412-6C, Library of Congress No. 78-70857, pp. 125-139, shows methods for addition of P&gt;2 numbers, each encoded as a vector of digits (digit vector) of length N. It shows a carry-lookahead adder tree and a carry-save adder tree.
"High-Speed Multiplication and Multiple Summand Addition" by R. S. Lim, Proceedings 4th Symposium on Computer Arithmetic, Oct. 25-27, 1978, IEEE Catalog No. 78 CH 1412-6C, Library of Congress No. 78-70857, pp. 149-153, discusses the problem of highspeed multiplication from the viewpoint of summand generation and summand summation.
Multiplication of large binary numbers in digital data processing machines is a time consuming operation. The computers usually execute the multiply operation by repetitive addition, and the time required is dependent on the number of additions required. Many structures have been provided for the multiply operation. Present systems usually provide a multiplication system wherein a plurality of multiplier binary bits are examined simultaneously to thereby cause multiples of a multiplicand to be added to a previously generated partial product. One such form of this type of multiply structure for binary numbers is shown in U.S. Pat. No. 3,515,344 entitled "Apparatus for Accumulating the Sum of a Plurality of Operands" by R. E. Goldschmidt et al, filed Aug. 31, 1966 and issued June 2, 1970, said patent being assigned to the assignee of the present application.
In this prior multiply apparatus, a plurality of carry save adder stages, each comprised of one or more carry save adder units are arranged in a configuration which permits the summation of a plurality of plural-binary bit operands. A first plurality of carry save adder stages is arranged to reduce six operands to a first output signal representing the sum and a second output signal representing carries. A second plurality of carry save adder stages are arranged in loop fashion such that the carry and sum output of the second plurality of stages are combined with the carry and sum outputs from the first plurality of stages at the input to the second plurality of stages. Certain of the carry save adder stages are comprised of latching means to retain the data for a specified period of time. Signal delays through the second plurality of stages and the time between timing pulse inputs to the other latch stages are equal such that the outputs from the second plurality of stages representing the sum of the first plurality of operands will combine with the outputs of the first plurality of stages representing the sum of a second plurality of operands. The timing pulses, circuit delays, and latched stages permit the application of operands to the input of the adder arrangement at a rate equal to that of the delay through only the second plurality of carry save adder stages.
There was difficulty in fitting the high speed multiply apparatus as shown in the above-mentioned U.S. Pat. No. 3,515,344 in the circuit module for the CPU because such as previous multiply apparatus required all carry and sum outputs of the carry-save adder tree on one chip to be wrapped around to the input of the carry-save adder tree on another chip. Also, latch circuits were required for the carry outputs of the carry-save adder tree.